#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
// 2476. 二叉搜索树最近节点查询
// 给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。
//请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x):val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {}
};
class Solution {
public:
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {

    }

private:
    // 小于等于 target 的 最大值
    int min_i(vector<int>& vec, int target) {
        int low = 0, high = vec.size() - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(vec[mid] == target) {
                return vec[mid];
            } else if(vec[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if(low == vec.size()) {
            return vec[vec.size()-1];
        } else if(high < 0) {
            return -1;
        } else {

        }
    }
    // 大于等于 target 的 最小值
    int max_i(vector<int>& vec, int target) {

    }
};
int main() {
    vector<int> sorted({1,2,4,6,9,13,15});
    int target = 16;
    auto lb = lower_bound(sorted.begin(),sorted.end(),target);
    cout << "lower_bound:" << *lb << endl;
    if(lb == sorted.end()) {
        cout << "not found" << endl;
        return 0;
    }
    int max = -1, min = -1;
    if(lb != sorted.end()) {
        max = *lb;
        if(max == target)
            min = max;
        else {
            lb--;
            min = *lb;
        }
    }
    cout << "min = " << min << ",max = " << max << endl;
//    auto ub = upper_bound(sorted.begin(),sorted.end(),5);
//    cout << "upper_bound:" << *ub << endl;
    return 0;
}
